package task1;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-06-04
 * Time:15:09
 */
    class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public class BinaryTree {
        public TreeNode root;//二叉树的根节点

        /**
         * 这种方式 是穷举的方式创建的
         * 但是 这样写不行 太low了。
         * @return
         */
        public void createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            /*TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;*/
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            D.left=F;
            this.root=A;
        }

        //前序遍历
        public void preOrder(TreeNode root){
            if(root==null){
                return;
            }
            System.out.println(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }

        //  子问题思路
        public List<Character> preorderTraversal(TreeNode root) {
            List<Character> ret=new ArrayList<>();
            if(root==null){
                return ret;
            }
            ret.add(root.val);
            List<Character> leftTree=preorderTraversal(root.left);
            ret.addAll(leftTree);
            List<Character> rightTree=preorderTraversal(root.right);
            ret.addAll(rightTree);
            return ret;
        }

        //中序遍历
        public void inOrder(TreeNode root){
            if(root==null){
                return;
            }

            inOrder(root.left);
            System.out.println(root.val);
            inOrder(root.right);
        }

        //后序遍历
        public void postOrder(TreeNode root){
            if(root==null){
                return;
            }

            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.val);
        }
        /**
         * 求节点个数
         * @param root
         * @return
         */
        public int size(TreeNode root){
            if(root==null){
                return 0;
            }
            return size(root.left)+size(root.right)+1;
        }

        /**
         * 子问题思路，求叶子结点的个数
         * @param root
         * @return
         */
        public int leafSize(TreeNode root){
            if(root == null){
                return 0;
            }
            if(root.left==null&&root.right==null){
                return 1;
            }
                return leafSize(root.left)+leafSize(root.right);
        }

//        int getLeafNodeCount2(TreeNode root) {
//            if(root == null) {
//                return 0;
//            }
//            if(root.left == null && root.right == null) {
//                //当前的root是叶子节点
//                return 1;
//            }
//            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
//        }

        /**
         * 子问题思路，求第k层叶子节点个数
         * @param root
         * @return
         */
        int getKLevelSize(TreeNode root,int k){
            if(root==null){
                return 0;
            }else if(k==1){
                if(root.left==null&&root.right==null){
                    return 1;
                }
            }
            return getKLevelSize(root.left, k-1)+getKLevelSize(root.right,k-1);
        }

        /**
         * 子问题思路，求树的高度
         * @param root
         * @return
         */
        int getHeight(TreeNode root){
            if(root==null){
                return 0;
            }
            return (Math.max(getHeight(root.left),getHeight(root.right))+1);
        }

        /**
         * 子问题思路，找到某个节点
         * @param root
         * @param val
         * @return
         */
        TreeNode find(TreeNode root, char val){
            if(root==null){
                return null;
            }
            if(root.val==val){
                return root;
            }
           TreeNode ret=find(root.left,val);
            if(ret!=null){
                return ret;
            }
            ret=find(root.right, val);
            if(ret!=null){
                return ret;
            }
            return null;
        }
//        boolean isCompleteTree(TreeNode root){
//            if(root==null){
//                return false;
//            }
//            Queue<TreeNode> queue=new LinkedList<TreeNode>();
//            queue.add(root)
//        }

        //层序遍历
        void levelOrder(TreeNode root){
            if (root==null){
                return ;
            }
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode cur=queue.poll();
                System.out.print(cur.val+" ");
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }


        public boolean getPath(TreeNode root, TreeNode node, List<TreeNode> list){
            if(root==null||node==null){
                return false;
            }
            if(root==node){
                list.add(root);
                return true;
            }
            boolean flg1=getPath(root.left,node,list);
            if(flg1){
                list.add(root);
            }
            boolean flg2=getPath(root.right, node, list);
            if(flg2){
                list.add(root);
            }
            return flg1||flg2;
        }
    }
